package primary.code08;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

/**
 * 问题
 * <p>
 * 设计一个数据结构，使如下3个操作的时间复杂度都是O（1）：
 * insert（value）：如果数据集中不包含一个数值，则把它添加到数据集中。
 * remove（value）：如果数据集中包含一个数值，则把它删除。
 * getRandom()：随机返回数据集中的一个数值，要求数据集中每个数字被返回的概率都相同
 *
 * <p>
 * 分析
 * 1. JDK中提供的容器中，Hash 可以做到增删O(1)
 * 2. Hash 无法等概率随机返回对象，因此可以增加额外的存储结构“数组”，通过数组索引随机返回
 * 3. 通过数组索引随机返回的前提是，数组中的元素是连续无空隙的
 * 4. 为了确保数组连续无空隙，在移除元素时要做好特殊操作
 */
@Slf4j
public class Code01_RandomPool {

    static class RandomizedSet<T> {
        private Map<T, Integer> map = new HashMap<>();
        private ArrayList<T> list = new ArrayList<>();

        public void insert(T val) {
            if (map.containsKey(val)) {
                log.warn("{} is existed", val);
                return;
            }
            map.put(val, list.size());
            list.add(val);
        }

        public void remove(T val) {
            if (!map.containsKey(val)) {
                log.warn("{} is not existed", val);
                return;
            }
            int index = map.get(val);
            map.remove(val);
            map.put(list.get(list.size() - 1), index);
            list.set(index, list.get(list.size() - 1));
            list.remove(list.size() - 1);
        }

        public T getRandom() {
            if (list.isEmpty()) {
                return null;
            }
            int randomIndex = (int) (Math.random() * list.size());
            return list.get(randomIndex);
        }
    }

    public static void main(String[] args) {
        Code01_RandomPool.RandomizedSet<String> randomizedSet = new RandomizedSet<>();
        randomizedSet.insert("A");
        randomizedSet.insert("B");
        randomizedSet.insert("C");
        randomizedSet.insert("C");
        randomizedSet.insert("D");
        randomizedSet.insert("E");
        randomizedSet.insert("E");
        randomizedSet.insert("F");
        randomizedSet.insert("G");

        randomizedSet.remove("C");
        randomizedSet.remove("E");

        log.info("get random: {}", randomizedSet.getRandom());
        log.info("get random: {}", randomizedSet.getRandom());
        log.info("get random: {}", randomizedSet.getRandom());
        log.info("get random: {}", randomizedSet.getRandom());
        log.info("get random: {}", randomizedSet.getRandom());
        log.info("get random: {}", randomizedSet.getRandom());
    }
}
